package vrp;

import java.util.Date;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Random;

import vrp.Array2DComparator;

public class Engine {
	//input
	private double vehicleCapacity = 100;
	private double[] demands;
	private double[][] distances;
	
	//output
	private double totalDistance = 0;
	private long totalTime = 0;
	ArrayList<ArrayList<Integer>> routes;
	
	public Engine(double vehicleCapacity, double[] demands, double[][] distances){
		this.vehicleCapacity = vehicleCapacity;
		this.demands = demands;
		this.distances = distances;
	}
	
	public double getTotalDistance(){
		return this.totalDistance;
	}
	
	public long getTotalTime(){
		return this.totalTime;
	}
	
	public ArrayList<ArrayList<Integer>> getRoutes(){
		return this.routes;
	}
	
	public void SavingHeuristics(){
		Date startTime = new Date();
		
		//initialisation
		int i, j, length = this.demands.length;
		double[] vehicleLoad = this.demands.clone();
		boolean[] start = new boolean[length];
		start[0] = false;
		int[] next = new int[length];
		next[0] = -1;
		this.totalDistance = 0;
		for (i=1;i<length;i++){
			start[i] = true;
			next[i] = 0;
			this.totalDistance += this.distances[0][i];
			this.totalDistance += this.distances[i][0];
		}
		
		if (length > 2){ //have more than 1 customer
			//start optimising
			double[][] savings = new double[(length-1)*(length-1)-(length-1)][4];
			int savingsIndex = -1;
			for (i=1;i<length;i++){
				for (j=1;j<length;j++){
					if (i!=j){
						savingsIndex++;
						savings[savingsIndex][0] = i; //from
						savings[savingsIndex][1] = j; //to
						savings[savingsIndex][2] = this.distances[i][0]+this.distances[0][j]-this.distances[i][j];
						savings[savingsIndex][3] = 0.0; //not used
					}
				}
			}
			Arrays.sort(savings, new Array2DComparator(2,1)); //need to sort Ascending
			while (savingsIndex >= 0){
				double isused = savings[savingsIndex][3];
				int from = (int)savings[savingsIndex][0];
				int to = (int)savings[savingsIndex][1];
				if (start[to]==true && next[from]==0){
					double savedDistance = savings[savingsIndex][2];
					i = to;
					while (next[i] != 0){
						i = next[i];
					}
					if (i!=from && vehicleLoad[i]+vehicleLoad[from]<=this.vehicleCapacity){ //can merge
						vehicleLoad[i] += vehicleLoad[from];
						vehicleLoad[from] = 0;
						start[to] = false;
						next[from] = to;
						this.totalDistance -= savedDistance;
						//for (j=0;j<savingsIndex;j++){
						//	if (savings[j][0] == from || savings[j][1] == to){
						//		savings[j][3] = 1;
						//	}
						//}
					}
				}
				savingsIndex--;
			}
		}
		
		//build routes
		this.routes = new ArrayList<ArrayList<Integer>>();
		for (i=1;i<length;i++){
			if (start[i] == true) {
				ArrayList<Integer> route = new ArrayList<Integer>();
				route.add(new Integer(0));
				j = i;
				//while (j != 0) {
				while (j > 0) {
					route.add(new Integer(j));
					j = next[j];
				}
				route.add(new Integer(0));
				this.routes.add(route);
			}
		}
		
		Date endTime = new Date();
		this.totalTime = endTime.getTime() - startTime.getTime();
	}
	
	public void GRASPMetaHeuristics(){
		Date startTime = new Date();
		
		//Initialisation
		double MAXDOUBLE = 99999999;
		int RESTRICTEDNUM = 3;
		int NUMREPEAT = 5;
		double bestDistance = MAXDOUBLE;
		ArrayList<ArrayList<Integer>> bestRoutes = new ArrayList<ArrayList<Integer>>();
		
		for (int repeat=0; repeat<NUMREPEAT; repeat++){
			int i, j;
			int numCustomers = this.demands.length;
			int numServed = 1;
			this.totalDistance = 0;
			
			boolean[] served = new boolean[numCustomers];
			served[0] = true;
			double totalDemand = 0;
			for (i = 1; i < numCustomers; i++) {
				totalDemand += this.demands[i];
				served[i] = false;
			}
			
			int lowerBoundVehicle = (int)Math.floor(totalDemand/this.vehicleCapacity)+1;
			double[] currentCapacity = new double[lowerBoundVehicle]; 
			this.routes = new ArrayList<ArrayList<Integer>>();
			
			//Construct the initial routes with seed customers
			for (i = 0; i < lowerBoundVehicle; i++) {
				//Search for unserved customer with max(min(distance)) to other served customers)
				int maxIndex = 0;
				double maxValue = -1;
				for (j = 1; j < numCustomers; j++) {
					if (served[j] == false){
						double minValue = MAXDOUBLE;
						for (int k = 0; k < numCustomers; k++) {
							if (served[k] == true) {
								if (this.distances[j][k]+this.distances[k][j] < minValue) {
									minValue = this.distances[j][k] + this.distances[k][j];
								}
							}
						}
						if (minValue > maxValue) {
							maxValue = minValue;
							maxIndex = j;
						}
					}
				}
				numServed += 1;
				served[maxIndex] = true;
				ArrayList<Integer> route = new ArrayList<Integer>();
				route.add(new Integer(0));
				route.add(new Integer(maxIndex));
				route.add(new Integer(0));
				this.routes.add(route);
				currentCapacity[i]=this.demands[maxIndex];
				this.totalDistance += this.distances[0][maxIndex] + this.distances[maxIndex][0]; 
			}
			
			//Start filling in the unserved customers
			while (numServed < numCustomers) {
				double[][] candidateList = new double[numCustomers - numServed][5];;
				int candidateListIndex = 0;
				for (int n = 1; n < numCustomers; n++) {
					if (served[n] == false) {
						int[] tempInt = new int[2];
						double[] tempDouble = new double[2];
						this.GRASPInsertionPriority(n,this.routes,currentCapacity,tempInt,tempDouble);
						candidateList[candidateListIndex][0] = n; //customer index
						candidateList[candidateListIndex][1] = tempInt[0]; //route index
						candidateList[candidateListIndex][2] = tempInt[1]; //route position index
						candidateList[candidateListIndex][3] = tempDouble[0]; //route insertion priority
						candidateList[candidateListIndex][4] = tempDouble[1]; //route insertion cost
						candidateListIndex++;
					}
				}
				
				Arrays.sort(candidateList, new Array2DComparator(3,-1)); //need to sort Descending
				
				Random randomGenerator = new Random();
				int randomIndex = randomGenerator.nextInt(Math.min(RESTRICTEDNUM, candidateList.length));
				int customerIndex = (int)candidateList[randomIndex][0];
				int routeIndex = (int)candidateList[randomIndex][1];
				int routePositionIndex = (int)candidateList[randomIndex][2];
				double routeInsertionCost = candidateList[randomIndex][4];
				
				numServed += 1;
				served[customerIndex] = true;
				this.routes.get(routeIndex).add(routePositionIndex+1, new Integer(customerIndex));
				this.totalDistance += routeInsertionCost;
				currentCapacity[routeIndex] += this.demands[customerIndex];
			}
			
			if (this.totalDistance<bestDistance) {
				bestDistance = this.totalDistance;
				bestRoutes = this.routes;
			}
		}
		
		this.totalDistance = bestDistance;
		this.routes = bestRoutes;
		
		Date endTime = new Date();
		this.totalTime = endTime.getTime() - startTime.getTime();
	}
	
	private double GRASPInsertionCost(int n, int i, int j){
		return this.distances[i][n] + this.distances[n][j] - this.distances[i][j];
	}
	
	private void GRASPInsertionPosition(int n, int t, ArrayList<ArrayList<Integer>> newRoutes, double[] currentCapacity, int[] returnInt, double[] returnDouble) { 
		//To calculate the position with least insertion cost for customer n  in a tour t
		
		//Starts with assuming least insertion cost is at position 0
		int minIndex = 0;
		double minValue = this.GRASPInsertionCost(n,newRoutes.get(t).get(0),newRoutes.get(t).get(1));
		
		//Go through all the remaining positions
		for (int i = 1; i < newRoutes.get(t).size()-1; i++) {
			double insertionCost = this.GRASPInsertionCost(n,newRoutes.get(t).get(i),newRoutes.get(t).get(i+1));
			if (insertionCost < minValue) {
				minValue = insertionCost;
				minIndex = i;
			}
		}
		
		//[index in t, insertion cost]
		returnInt[0] = minIndex;
		returnDouble[0] = minValue;
		if (currentCapacity[t]+this.demands[n]>this.vehicleCapacity){
			returnDouble[0] = 99999999;
		}
	}
	
	private void GRASPInsertionPriority(int n, ArrayList<ArrayList<Integer>> newRoutes, double[] currentCapacity, int[] returnInt, double[] returnDouble) { 
		//To calculate insertion priority for customer n
		
		//Starts with assuming least insertion cost is at route 0
		int minRoute = 0;
		int numberProcessed = 1;
		double insertionPriority = 0;

		int[] tempInt = new int[1];
		double[] tempDouble = new double[1];
		this.GRASPInsertionPosition(n,0,newRoutes,currentCapacity,tempInt,tempDouble);
		int minRouteIndex = tempInt[0];
		double minRouteValue = tempDouble[0];
		
		//Go through all the remaining routes
		for (int t = 1; t < newRoutes.size(); t++) {
			this.GRASPInsertionPosition(n,t,newRoutes,currentCapacity,tempInt,tempDouble);
			int tempRouteIndex = tempInt[0];
			double tempRouteValue = tempDouble[0];
			
			if (tempRouteValue < minRouteValue) {
				insertionPriority += (minRouteValue - tempRouteValue) * numberProcessed;
				minRoute = t;
				minRouteIndex = tempRouteIndex;
				minRouteValue = tempRouteValue;
			} else {
				insertionPriority += (tempRouteValue - minRouteValue);
			}
			numberProcessed += 1;
		}
		
		//[insertionPriority, tour index, position index in tour]
		returnInt[0] = minRoute;
		returnInt[1] = minRouteIndex;
		returnDouble[0] = insertionPriority;
		returnDouble[1] = minRouteValue;
	}
}
